home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_12_08 / treu / uflood.c < prev    next >
Text File  |  1994-04-25  |  3KB  |  157 lines
  1. /*****************************************************
  2.  * UFLOOD.C - unoptimized flood visit
  3.  *
  4.  * for ANSI C
  5.  *
  6.  * by Anton Treuenfels
  7.  * last revision:  04/12/94
  8.  *****************************************************/
  9.  
  10. /*****************************
  11.  * HEADER SECTION - UFLOOD.H *
  12.  *****************************/
  13.  
  14. #ifndef SEEN_UFLOOD
  15. #define SEEN_UFLOOD
  16.  
  17. /* function prototype */
  18.  
  19. int uflood(int, int, int (*)(int, int));
  20.  
  21. #endif
  22.  
  23. /***************************
  24.  * CODE SECTION - UFLOOD.C *
  25.  ***************************/
  26.  
  27. #include <stdlib.h>
  28.  
  29. #include "usrdef.h"
  30.  
  31. /* line shadow */
  32.  
  33. typedef struct shdw {
  34.     struct shdw *next;      /* forward link */
  35.     int lft, rgt;           /* endpoints */
  36.     int row, par;           /* row and parent row */
  37.     Boolean ok;             /* valid flag */
  38. } shadow;
  39.  
  40. /* shadow variables */
  41.  
  42. static shadow *seedShadow;  /* current shadow */
  43. static shadow *shadowHead;  /* other pending shadows */
  44.  
  45. /* visit coordinate function */
  46.  
  47. static int (*isInterior)(int, int);
  48.  
  49. /*****************************************************/
  50.  
  51. /* make new shadow */
  52.  
  53. static void newshadow(int slft, int srgt,
  54.          int srow, int prow) {
  55.  
  56.     shadow *new;
  57.  
  58.     if ((new = malloc(sizeof(shadow))) == NULL)
  59.         exit(EXIT_FAILURE);
  60.  
  61.     new->lft = slft;    new->rgt = srgt;
  62.     new->row = srow;    new->par = prow;
  63.     new->ok = TRUE;
  64.     new->next = shadowHead;
  65.     shadowHead = new;
  66. }
  67.  
  68. /* clip off ends of overlapped shadow */
  69.  
  70. static void clipshadow(shadow *s, shadow *clip) {
  71.  
  72.     if (s->lft < (clip->lft - 1))
  73.         newshadow(s->lft, clip->lft - 2, s->row, s->par);
  74.     if (s->rgt > (clip->rgt + 1))
  75.         newshadow(clip->rgt + 2, s->rgt, s->row, s->par);
  76. }
  77.  
  78. /* remove overlapped segment from shadow pair */
  79.  
  80. static void removeoverlap(shadow *o) {
  81.  
  82.     shadow *s;
  83.  
  84.     for (s = shadowHead; s; s = s->next) {
  85.         if ((s->row == o->par) && (s->ok) &&
  86.             (s->lft <= o->rgt) && (s->rgt >= o->lft)) {
  87.                 clipshadow(s, o);
  88.                 if (o != seedShadow)
  89.                     clipshadow(o, s);
  90.                 s->ok = o->ok = FALSE;
  91.                 return;
  92.         }
  93.     }
  94. }
  95.  
  96. /* make shadows of one child line */
  97.  
  98. static void makeshadows(int lft, int rgt, int row) {
  99.  
  100.     shadow *p;
  101.  
  102.     newshadow(lft, rgt, row + 1, row);
  103.     newshadow(lft, rgt, row - 1, row);
  104.  
  105.     removeoverlap(seedShadow);
  106.  
  107.     for (p = shadowHead; p; p = p->next) {
  108.         if ((p->row == row) && (p->ok) &&
  109.                 !((p->lft > rgt) || (p->rgt < lft)))
  110.             removeoverlap(p);
  111.     }
  112. }
  113.  
  114. /* fill all child lines found within one shadow */
  115.  
  116. static void fillshadow(void) {
  117.  
  118.     int col, row, lft;
  119.  
  120.     row = seedShadow->row;
  121.  
  122.     for (col = seedShadow->lft; col <= seedShadow->rgt;
  123.              col++) {
  124.         if ((*isInterior)(col, row)) {
  125.             if ((lft = col) == seedShadow->lft) {
  126.                 while ((*isInterior)(--lft, row))
  127.                     ;
  128.                 lft++;
  129.             }
  130.             while ((*isInterior)(++col, row))
  131.                 ;
  132.  
  133.             makeshadows(lft, col - 1, row);
  134.         }
  135.     }
  136. }
  137.  
  138. /* flood visit */
  139.  
  140. int uflood(int seedx, int seedy,
  141.         int (*visit)(int, int)) {
  142.  
  143.     isInterior = visit;
  144.     shadowHead = NULL;
  145.     newshadow(seedx, seedx, seedy, seedy);
  146.     while (shadowHead) {
  147.         seedShadow = shadowHead;
  148.         shadowHead = shadowHead->next;
  149.         if (seedShadow->ok)
  150.             fillshadow();
  151.         free(seedShadow);
  152.     }
  153. }
  154.  
  155.  
  156.  
  157.